package d2;
import java.util.*;
public class Day6 {
    public static void main(String[] args) {

    }
    //岛屿的最大数量bfs
    public int maxAreaOfIsland(int[][] grid) {
            int m = grid.length,n = grid[0].length;
            int[] dx = {1,-1,0,0};
            int[] dy = {0,0,-1,1};
            boolean[][] ck = new boolean[m][n];
            Queue<int[]> queue = new LinkedList<>();
            int ret = 0;
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(grid[i][j]==1 && !ck[i][j]) {
                        int tmp = 1;
                        queue.add(new int[]{i,j});
                        ck[i][j]=true;
                        while(!queue.isEmpty()) {
                            int sz = queue.size();
                            for(int s=sz;s>0;s--) {
                                int[] t = queue.poll();
                                int a = t[0];
                                int b = t[1];
                                for(int k=0;k<4;k++) {
                                    int x = a + dx[k];
                                    int y = b + dy[k];
                                    if(x>=0&&x<m&&y>=0&&y<n && grid[x][y]==1&&!ck[x][y]) {
                                        tmp++;
                                        ck[x][y]=true;
                                        queue.add(new int[]{x,y});
                                    }
                                }
                            }
                        }
                        ret = Math.max(tmp,ret);
                    }
                }
            }
            return ret;
        }

    //岛屿数量
    public int numIslands(char[][] grid) {
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int m = grid.length, n = grid[0].length;
        boolean[][] ck = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int ret = 0;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]=='1' && !ck[i][j]) {
                    ret++;
                    queue.add(new int[]{i,j});
                    while(!queue.isEmpty()) {
                        int sz = queue.size();
                        for(int size=sz;size>0;size--){
                            int[] t = queue.poll();
                            int a = t[0];
                            int b = t[1];
                            for(int k=0;k<4;k++) {
                                int x = a + dx[k];
                                int y = b + dy[k];
                                if(x>=0&&x<m&&y>=0&&y<n && grid[x][y]=='1'&&!ck[x][y]) {
                                    ck[x][y]=true;
                                    queue.add(new int[]{x,y});
                                }
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }

    //图像渲染bfs
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        //if(image[sr][sc]==color) return image;
        int val = image[sr][sc];
        int m=image.length,n=image[0].length;
        boolean[][] ck = new boolean[m][n];
        image[sr][sc]=color;
        ck[sr][sc]=true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr,sc});
        while(!queue.isEmpty()) {
            int sz = queue.size();
            for(int i=sz;i>0;i--) {
                int[] t = queue.poll();
                int a = t[0];
                int b = t[1];
                for(int k=0;k<4;k++) {
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if(x<m&&x>=0&&y>=0&&y<n && !ck[x][y]&&image[x][y]==val) {
                        image[x][y]=color;
                        ck[x][y]=true;
                        queue.add(new int[]{x,y});
                    }
                }
            }
        }
        return image;
    }

}
